/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2020年03月02日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2020 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();

        vector<vector<int>> dp(amount+1, vector<int>(n+1, 0));
        for(int i = 0; i <= n; i++){
            dp[0][i] = 1;
        }

        for(int i = 1; i <= amount; i++){
            for(int j = 1; j <= n; j++){
                dp[i][j] = dp[i][j-1];
                if( i - coins[j-1] >= 0 ){
                    dp[i][j] += dp[i-coins[j-1]][j];
                }
            }
        }

        return dp[amount][n];
    }
};

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();

        vector<int> dp(amount+1, 0);
        dp[0] = 1;

        for(int i = 0; i < n; i++){
            for(int j = coins[i]; j <= amount; j++){
                dp[j] += dp[j-coins[i]];
            }
        }

        return dp[amount];
    }
};